import java.util.ArrayList;

/**
 *
 * @author Santos
 */
public class AlgoritmoDijkstra {

    private int INFINITO = 9999999;
    private int raiz;
    private int num_vertices;
    private int peso[];
    private int antecessor[];
    private int[][] matriz;
    private int ultimoNoEmS;

    //lista de adjacencia de u é exatamente a linha de u na matriz
    private ArrayList<Integer> conjunto_s; //conjunto que conterá os nós já verificados
    private ArrayList<Integer> conjunto_A; //conjunto que contém os nós ainda não verificado

    public AlgoritmoDijkstra(int[][] matrizAdjacencia, int raiz, int quantidadeDeVertices) {
        this.raiz = raiz;
        num_vertices = quantidadeDeVertices;//matrizAdjacencia.length;
        peso = new int[num_vertices];
        antecessor = new int[num_vertices];
        conjunto_s = new ArrayList<Integer>();
        conjunto_A = new ArrayList<Integer>();
        matriz = matrizAdjacencia;//a matriz de adjacencia
        //num_vertices = quantidadeDeVertices;
    }

    public void dijkstra() {
        for (int v = 0; v < num_vertices; v++) {
            peso[v] = INFINITO;
            antecessor[v] = -1;
        }
        //this.imprimeVetor();
        this.inicializaConjuntos();

        peso[raiz] = 0; //nó de início
        //ultimoNoAChegarEmS = raiz;
        int v, i;// = 0;
        while (!conjunto_A.isEmpty()) {

                v = conjunto_A.get(0);
                i = 0;
                while (i < conjunto_A.size()) {//for(; v < conjunto_A.size() ; v++){
                    //Se v é adjacente a u e v ainda está no conjunto de vértices não verificados
                    if ((matriz[ultimoNoEmS][v] != INFINITO)){//&&(!conjunto_s.contains(v))) {//v é adjacente a u
                        if (peso[v] > peso[ultimoNoEmS] + matriz[ultimoNoEmS][v]) {
                            peso[v] = peso[ultimoNoEmS] + matriz[ultimoNoEmS][v];
                            antecessor[v] = ultimoNoEmS;
                        }
                    }
                    //imprimePeso();//imprime vetor peso
                    i++;
                    if (i < conjunto_A.size()) {
                        v = conjunto_A.get(i);
                    }else   break;
                }
                //imprimePeso();//imprime vetor peso
                this.minimoDeA();
            }
            
        }
    //}

    private void inicializaConjuntos() {
        conjunto_s.add(raiz);
        for (int j = 0; j < num_vertices; j++) {
            if (j != raiz) {                     //o nó raiz é o primeiro a ir pro conjunto S, então sai do conjunto A
                conjunto_A.add(j); //adiciona todos os nós no conjunto A, matriz[0][j] é o peso e não o nó
            }
        }
        ultimoNoEmS = raiz;
    }

    private void minimoDeA() {
        int pesoMin, indexMin, indexA = 0;  //pega o primeiro elemento
        int noDeA = conjunto_A.get(0); //retorna o nó

        pesoMin = peso[ noDeA ]; //pega o peso do primeiro no no conjunto A
        indexMin = noDeA;
        if(!conjunto_A.isEmpty()){
            for (indexA = 1; indexA < conjunto_A.size(); indexA++) {
                noDeA = conjunto_A.get(indexA);//recebe o nó, percorre o conjunto A
                if( peso[ noDeA ] < pesoMin){//if (matriz[ ultimoNoEmS][indexConj] < pesoMin) {//if( peso[ indexConj ] < pesoMin){
                    pesoMin = peso[ noDeA ];//matriz[ ultimoNoEmS][indexConj];//peso[ indexConj ];//retira-se o peso mínimo
                    indexMin = noDeA;
                }
            }
        //System.out.println("Peso minimo: "+pesoMin);
        //System.out.println("Index minimo: "+indexMin);
        //System.out.println("Entra em S: "+indexMin);//+conjunto_A.get(indexMin));
        ultimoNoEmS = indexMin;//conjunto_A.remove(indexMin);
        conjunto_s.add(ultimoNoEmS);//retira de A e coloca em S
        for(int j = 0; j < conjunto_A.size(); j++)
            if(conjunto_A.get(j)== indexMin){
                conjunto_A.remove(j);
                break;
            }
        }
    }

    public int[] vetorAntecessor() {
        return antecessor;
    }

    public void imprimeVetor(){
        System.out.printf("Vetor antecessor: [");
        for(int a = 0; a < antecessor.length ; a++)
            System.out.printf(" %d ", antecessor[a] );
        System.out.println(" ]");
    }
    public void imprimeA(){
        System.out.printf("Conjunto A: [");
        for(int a = 0; a < conjunto_A.size() ; a++)
            System.out.printf(" %d ", conjunto_A.get(a) );
        System.out.println(" ]");
    }
    public void imprimeS(){
        System.out.printf("Conjunto S: [");
        for(int a = 0; a < conjunto_s.size() ; a++)
            System.out.printf(" %d ", conjunto_s.get(a) );
        System.out.println(" ]");
    }
    public void imprimePeso(){
        System.out.printf("Vetor peso: [");
        for(int a = 0; a < peso.length ; a++)
            System.out.printf(" %d ", peso[a] );
        System.out.println(" ]");
    }
    /**
     *
     * @param orig
     * @param dest
     * @return
     */
    public int enviarpara(int orig, int dest) {
        int dest2;
        if(antecessor[dest] == orig)//
            return dest;

        dest2 = antecessor[dest];
        while (dest2 != orig) { //orig é a raiz
            dest = dest2;
            dest2 = antecessor[dest2];
            if (dest2 == orig) {
                break;
            }
        }
        return dest;
    }
}